# -*- encoding: utf-8 -*-
import datetime
import time


def insert_sort_v1(data):
    unsort = data[1:]
    unsort_length = len(unsort)
    sorted = [data[0]]
    for i in range(unsort_length):
        for j in range(len(sorted)):
            if sorted[j] > unsort[i]:
                sorted.insert(j, unsort[i])
                break
        else:
            sorted.append(unsort[i])
    return sorted


def insertion_sort_v2(collection):
    """
    [9, 2, 3, 4, 6, 7, 8, 1, 4]
    [2, 9, 3, 4, 6, 7, 8, 1, 4]
    [2, 3, 9, 4, 6, 7, 8, 1, 4]
    [2, 3, 4, 9, 6, 7, 8, 1, 4]
    [2, 3, 4, 6, 9, 7, 8, 1, 4]
    [2, 3, 4, 6, 7, 9, 8, 1, 4]
    [2, 3, 4, 6, 7, 8, 9, 1, 4]
    [2, 3, 4, 6, 7, 8, 1, 9, 4]
    [2, 3, 4, 6, 7, 1, 8, 9, 4]
    [2, 3, 4, 6, 1, 7, 8, 9, 4]
    [2, 3, 4, 1, 6, 7, 8, 9, 4]
    [2, 3, 1, 4, 6, 7, 8, 9, 4]
    [2, 1, 3, 4, 6, 7, 8, 9, 4]
    [1, 2, 3, 4, 6, 7, 8, 9, 4]
    [1, 2, 3, 4, 6, 7, 8, 4, 9]
    [1, 2, 3, 4, 6, 7, 4, 8, 9]
    [1, 2, 3, 4, 6, 4, 7, 8, 9]
    [1, 2, 3, 4, 4, 6, 7, 8, 9]
    """

    for loop_index in range(1, len(collection)):
        insertion_index = loop_index
        while insertion_index > 0 and collection[insertion_index - 1] > collection[insertion_index]:
            collection[insertion_index], collection[insertion_index - 1] = collection[insertion_index - 1], collection[
                insertion_index]
            insertion_index -= 1

    return collection


if __name__ == '__main__':
    print('input unsort list:')
    a1 = input()  # 9,2,3,4,6,7,8,1,4
    a1 = [int(x) for x in a1.split(',')]
    print(insert_sort_v1(a1))
    print(insertion_sort_v2(a1))
